// Protocol Buffers - Google's data interchange format
// Copyright 2008 Google Inc.  All rights reserved.
// https://developers.google.com/protocol-buffers/
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include <google/protobuf/util/field_mask_util.h>

#include <google/protobuf/stubs/strutil.h>
#include <google/protobuf/stubs/map_util.h>

#ifdef _MSC_VER

#pragma warning(disable: 4018)
#endif //_MSC_VER

namespace google {
	namespace protobuf {
		namespace util {

			using google::protobuf::FieldMask;

			string FieldMaskUtil::ToString(const FieldMask& mask) {
				return Join(mask.paths(), ",");
			}

			void FieldMaskUtil::FromString(StringPiece str, FieldMask* out) {
				out->Clear();
				std::vector<string> paths = Split(str, ",");
				for (int i = 0; i < paths.size(); ++i) {
					if (paths[i].empty()) continue;
					out->add_paths(paths[i]);
				}
			}

			bool FieldMaskUtil::SnakeCaseToCamelCase(StringPiece input, string* output) {
				output->clear();
				bool after_underscore = false;
				for (int i = 0; i < input.size(); ++i) {
					if (input[i] >= 'A' && input[i] <= 'Z') {
						// The field name must not contain uppercase letters.
						return false;
					}
					if (after_underscore) {
						if (input[i] >= 'a' && input[i] <= 'z') {
							output->push_back(input[i] + 'A' - 'a');
							after_underscore = false;
						}
						else {
							// The character after a "_" must be a lowercase letter.
							return false;
						}
					}
					else if (input[i] == '_') {
						after_underscore = true;
					}
					else {
						output->push_back(input[i]);
					}
				}
				if (after_underscore) {
					// Trailing "_".
					return false;
				}
				return true;
			}

			bool FieldMaskUtil::CamelCaseToSnakeCase(StringPiece input, string* output) {
				output->clear();
				for (int i = 0; i < input.size(); ++i) {
					if (input[i] == '_') {
						// The field name must not contain "_"s.
						return false;
					}
					if (input[i] >= 'A' && input[i] <= 'Z') {
						output->push_back('_');
						output->push_back(input[i] + 'a' - 'A');
					}
					else {
						output->push_back(input[i]);
					}
				}
				return true;
			}

			bool FieldMaskUtil::ToJsonString(const FieldMask& mask, string* out) {
				out->clear();
				for (int i = 0; i < mask.paths_size(); ++i) {
					const string& path = mask.paths(i);
					string camelcase_path;
					if (!SnakeCaseToCamelCase(path, &camelcase_path)) {
						return false;
					}
					if (i > 0) {
						out->push_back(',');
					}
					out->append(camelcase_path);
				}
				return true;
			}

			bool FieldMaskUtil::FromJsonString(StringPiece str, FieldMask* out) {
				out->Clear();
				std::vector<string> paths = Split(str, ",");
				for (int i = 0; i < paths.size(); ++i) {
					if (paths[i].empty()) continue;
					string snakecase_path;
					if (!CamelCaseToSnakeCase(paths[i], &snakecase_path)) {
						return false;
					}
					out->add_paths(snakecase_path);
				}
				return true;
			}

			bool FieldMaskUtil::GetFieldDescriptors(
				const Descriptor* descriptor, StringPiece path,
				std::vector<const FieldDescriptor*>* field_descriptors) {
				if (field_descriptors != NULL) {
					field_descriptors->clear();
				}
				std::vector<string> parts = Split(path, ".");
				for (int i = 0; i < parts.size(); ++i) {
					const string& field_name = parts[i];
					if (descriptor == NULL) {
						return false;
					}
					const FieldDescriptor* field = descriptor->FindFieldByName(field_name);
					if (field == NULL) {
						return false;
					}
					if (field_descriptors != NULL) {
						field_descriptors->push_back(field);
					}
					if (!field->is_repeated() &&
						field->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE) {
						descriptor = field->message_type();
					}
					else {
						descriptor = NULL;
					}
				}
				return true;
			}

			void FieldMaskUtil::InternalGetFieldMaskForAllFields(
				const Descriptor* descriptor, FieldMask* out) {
				for (int i = 0; i < descriptor->field_count(); ++i) {
					out->add_paths(descriptor->field(i)->name());
				}
			}

			namespace {
				// A FieldMaskTree represents a FieldMask in a tree structure. For example,
				// given a FieldMask "foo.bar,foo.baz,bar.baz", the FieldMaskTree will be:
				//
				//   [root] -+- foo -+- bar
				//           |       |
				//           |       +- baz
				//           |
				//           +- bar --- baz
				//
				// In the tree, each leaf node represents a field path.
				class FieldMaskTree {
				public:
					FieldMaskTree();
					~FieldMaskTree();

					void MergeFromFieldMask(const FieldMask& mask);
					void MergeToFieldMask(FieldMask* mask);

					// Add a field path into the tree. In a FieldMask, each field path matches
					// the specified field and also all its sub-fields. If the field path to
					// add is a sub-path of an existing field path in the tree (i.e., a leaf
					// node), it means the tree already matches the given path so nothing will
					// be added to the tree. If the path matches an existing non-leaf node in the
					// tree, that non-leaf node will be turned into a leaf node with all its
					// children removed because the path matches all the node's children.
					void AddPath(const string& path);

					// Remove a path from the tree.
					// If the path is a sub-path of an existing field path in the tree, it means
					// we need remove the existing fied path and add all sub-paths except
					// specified path. If the path matches an existing node in the tree, this node
					// will be moved.
					void RemovePath(const string& path, const Descriptor* descriptor);

					// Calculate the intersection part of a field path with this tree and add
					// the intersection field path into out.
					void IntersectPath(const string& path, FieldMaskTree* out);

					// Merge all fields specified by this tree from one message to another.
					void MergeMessage(const Message& source,
						const FieldMaskUtil::MergeOptions& options,
						Message* destination) {
						// Do nothing if the tree is empty.
						if (root_.children.empty()) {
							return;
						}
						MergeMessage(&root_, source, options, destination);
					}

					// Add required field path of the message to this tree based on current tree
					// structure. If a message is present in the tree, add the path of its
					// required field to the tree. This is to make sure that after trimming a
					// message with required fields are set, check IsInitialized() will not fail.
					void AddRequiredFieldPath(const Descriptor* descriptor) {
						// Do nothing if the tree is empty.
						if (root_.children.empty()) {
							return;
						}
						AddRequiredFieldPath(&root_, descriptor);
					}

					// Trims all fields not specified by this tree from the given message.
					void TrimMessage(Message* message) {
						// Do nothing if the tree is empty.
						if (root_.children.empty()) {
							return;
						}
						TrimMessage(&root_, message);
					}

				private:
					struct Node {
						Node() {}

						~Node() { ClearChildren(); }

						void ClearChildren() {
							for (std::map<string, Node*>::iterator it = children.begin();
								it != children.end(); ++it) {
								delete it->second;
							}
							children.clear();
						}

						std::map<string, Node*> children;

					private:
						GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(Node);
					};

					// Merge a sub-tree to mask. This method adds the field paths represented
					// by all leaf nodes descended from "node" to mask.
					void MergeToFieldMask(const string& prefix, const Node* node, FieldMask* out);

					// Merge all leaf nodes of a sub-tree to another tree.
					void MergeLeafNodesToTree(const string& prefix, const Node* node,
						FieldMaskTree* out);

					// Merge all fields specified by a sub-tree from one message to another.
					void MergeMessage(const Node* node, const Message& source,
						const FieldMaskUtil::MergeOptions& options,
						Message* destination);

					// Add required field path of the message to this tree based on current tree
					// structure. If a message is present in the tree, add the path of its
					// required field to the tree. This is to make sure that after trimming a
					// message with required fields are set, check IsInitialized() will not fail.
					void AddRequiredFieldPath(Node* node, const Descriptor* descriptor);

					// Trims all fields not specified by this sub-tree from the given message.
					void TrimMessage(const Node* node, Message* message);

					Node root_;

					GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(FieldMaskTree);
				};

				FieldMaskTree::FieldMaskTree() {}

				FieldMaskTree::~FieldMaskTree() {}

				void FieldMaskTree::MergeFromFieldMask(const FieldMask& mask) {
					for (int i = 0; i < mask.paths_size(); ++i) {
						AddPath(mask.paths(i));
					}
				}

				void FieldMaskTree::MergeToFieldMask(FieldMask* mask) {
					MergeToFieldMask("", &root_, mask);
				}

				void FieldMaskTree::MergeToFieldMask(const string& prefix, const Node* node,
					FieldMask* out) {
					if (node->children.empty()) {
						if (prefix.empty()) {
							// This is the root node.
							return;
						}
						out->add_paths(prefix);
						return;
					}
					for (std::map<string, Node*>::const_iterator it = node->children.begin();
						it != node->children.end(); ++it) {
						string current_path = prefix.empty() ? it->first : prefix + "." + it->first;
						MergeToFieldMask(current_path, it->second, out);
					}
				}

				void FieldMaskTree::AddPath(const string& path) {
					std::vector<string> parts = Split(path, ".");
					if (parts.empty()) {
						return;
					}
					bool new_branch = false;
					Node* node = &root_;
					for (int i = 0; i < parts.size(); ++i) {
						if (!new_branch && node != &root_ && node->children.empty()) {
							// Path matches an existing leaf node. This means the path is already
							// coverred by this tree (for example, adding "foo.bar.baz" to a tree
							// which already contains "foo.bar").
							return;
						}
						const string& node_name = parts[i];
						Node*& child = node->children[node_name];
						if (child == NULL) {
							new_branch = true;
							child = new Node();
						}
						node = child;
					}
					if (!node->children.empty()) {
						node->ClearChildren();
					}
				}

				void FieldMaskTree::RemovePath(const string& path,
					const Descriptor* descriptor) {
					std::vector<string> parts = Split(path, ".");
					if (parts.empty()) {
						return;
					}
					std::vector<Node*> nodes(parts.size());
					Node* node = &root_;
					const Descriptor* current_descriptor = descriptor;
					Node* new_branch_node = NULL;
					for (int i = 0; i < parts.size(); ++i) {
						nodes[i] = node;
						const FieldDescriptor* field_descriptor =
							current_descriptor->FindFieldByName(parts[i]);
						if (field_descriptor == NULL ||
							(field_descriptor->cpp_type() != FieldDescriptor::CPPTYPE_MESSAGE &&
								i != parts.size() - 1)) {
							// Invalid path.
							if (new_branch_node != NULL) {
								// If add any new nodes, cleanup.
								new_branch_node->ClearChildren();
							}
							return;
						}

						if (node->children.empty()) {
							if (new_branch_node == NULL) {
								new_branch_node = node;
							}
							for (int i = 0; i < current_descriptor->field_count(); ++i) {
								node->children[current_descriptor->field(i)->name()] = new Node();
							}
						}
						if (ContainsKey(node->children, parts[i])) {
							node = node->children[parts[i]];
							if (field_descriptor->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE) {
								current_descriptor = field_descriptor->message_type();
							}
						}
						else {
							// Path does not exist.
							return;
						}
					}
					// Remove path.
					for (int i = parts.size() - 1; i >= 0; i--) {
						delete nodes[i]->children[parts[i]];
						nodes[i]->children.erase(parts[i]);
						if (!nodes[i]->children.empty()) {
							break;
						}
					}
				}

				void FieldMaskTree::IntersectPath(const string& path, FieldMaskTree* out) {
					std::vector<string> parts = Split(path, ".");
					if (parts.empty()) {
						return;
					}
					const Node* node = &root_;
					for (int i = 0; i < parts.size(); ++i) {
						if (node->children.empty()) {
							if (node != &root_) {
								out->AddPath(path);
							}
							return;
						}
						const string& node_name = parts[i];
						const Node* result = FindPtrOrNull(node->children, node_name);
						if (result == NULL) {
							// No intersection found.
							return;
						}
						node = result;
					}
					// Now we found a matching node with the given path. Add all leaf nodes
					// to out.
					MergeLeafNodesToTree(path, node, out);
				}

				void FieldMaskTree::MergeLeafNodesToTree(const string& prefix, const Node* node,
					FieldMaskTree* out) {
					if (node->children.empty()) {
						out->AddPath(prefix);
					}
					for (std::map<string, Node*>::const_iterator it = node->children.begin();
						it != node->children.end(); ++it) {
						string current_path = prefix.empty() ? it->first : prefix + "." + it->first;
						MergeLeafNodesToTree(current_path, it->second, out);
					}
				}

				void FieldMaskTree::MergeMessage(const Node* node, const Message& source,
					const FieldMaskUtil::MergeOptions& options,
					Message* destination) {
					GOOGLE_DCHECK(!node->children.empty());
					const Reflection* source_reflection = source.GetReflection();
					const Reflection* destination_reflection = destination->GetReflection();
					const Descriptor* descriptor = source.GetDescriptor();
					for (std::map<string, Node*>::const_iterator it = node->children.begin();
						it != node->children.end(); ++it) {
						const string& field_name = it->first;
						const Node* child = it->second;
						const FieldDescriptor* field = descriptor->FindFieldByName(field_name);
						if (field == NULL) {
							GOOGLE_LOG(ERROR) << "Cannot find field \"" << field_name << "\" in message "
								<< descriptor->full_name();
							continue;
						}
						if (!child->children.empty()) {
							// Sub-paths are only allowed for singular message fields.
							if (field->is_repeated() ||
								field->cpp_type() != FieldDescriptor::CPPTYPE_MESSAGE) {
								GOOGLE_LOG(ERROR) << "Field \"" << field_name << "\" in message "
									<< descriptor->full_name()
									<< " is not a singular message field and cannot "
									<< "have sub-fields.";
								continue;
							}
							MergeMessage(child, source_reflection->GetMessage(source, field), options,
								destination_reflection->MutableMessage(destination, field));
							continue;
						}
						if (!field->is_repeated()) {
							switch (field->cpp_type()) {
#define COPY_VALUE(TYPE, Name)                                              \
  case FieldDescriptor::CPPTYPE_##TYPE: {                                   \
    if (source_reflection->HasField(source, field)) {                       \
      destination_reflection->Set##Name(                                    \
          destination, field, source_reflection->Get##Name(source, field)); \
    } else {                                                                \
      destination_reflection->ClearField(destination, field);               \
    }                                                                       \
    break;                                                                  \
  }
								COPY_VALUE(BOOL, Bool)
									COPY_VALUE(INT32, Int32)
									COPY_VALUE(INT64, Int64)
									COPY_VALUE(UINT32, UInt32)
									COPY_VALUE(UINT64, UInt64)
									COPY_VALUE(FLOAT, Float)
									COPY_VALUE(DOUBLE, Double)
									COPY_VALUE(ENUM, Enum)
									COPY_VALUE(STRING, String)
#undef COPY_VALUE
							case FieldDescriptor::CPPTYPE_MESSAGE: {
									if (options.replace_message_fields()) {
										destination_reflection->ClearField(destination, field);
									}
									if (source_reflection->HasField(source, field)) {
										destination_reflection->MutableMessage(destination, field)
											->MergeFrom(source_reflection->GetMessage(source, field));
									}
									break;
								}
							}
						}
						else {
							if (options.replace_repeated_fields()) {
								destination_reflection->ClearField(destination, field);
							}
							switch (field->cpp_type()) {
#define COPY_REPEATED_VALUE(TYPE, Name)                            \
  case FieldDescriptor::CPPTYPE_##TYPE: {                          \
    int size = source_reflection->FieldSize(source, field);        \
    for (int i = 0; i < size; ++i) {                               \
      destination_reflection->Add##Name(                           \
          destination, field,                                      \
          source_reflection->GetRepeated##Name(source, field, i)); \
    }                                                              \
    break;                                                         \
  }
								COPY_REPEATED_VALUE(BOOL, Bool)
									COPY_REPEATED_VALUE(INT32, Int32)
									COPY_REPEATED_VALUE(INT64, Int64)
									COPY_REPEATED_VALUE(UINT32, UInt32)
									COPY_REPEATED_VALUE(UINT64, UInt64)
									COPY_REPEATED_VALUE(FLOAT, Float)
									COPY_REPEATED_VALUE(DOUBLE, Double)
									COPY_REPEATED_VALUE(ENUM, Enum)
									COPY_REPEATED_VALUE(STRING, String)
#undef COPY_REPEATED_VALUE
							case FieldDescriptor::CPPTYPE_MESSAGE: {
									int size = source_reflection->FieldSize(source, field);
									for (int i = 0; i < size; ++i) {
										destination_reflection->AddMessage(destination, field)
											->MergeFrom(
												source_reflection->GetRepeatedMessage(source, field, i));
									}
									break;
								}
							}
						}
					}
				}

				void FieldMaskTree::AddRequiredFieldPath(
					Node* node, const Descriptor* descriptor) {
					const int32 field_count = descriptor->field_count();
					for (int index = 0; index < field_count; ++index) {
						const FieldDescriptor* field = descriptor->field(index);
						if (field->is_required()) {
							const string& node_name = field->name();
							Node*& child = node->children[node_name];
							if (child == NULL) {
								// Add required field path to the tree
								child = new Node();
							}
							else if (child->children.empty()) {
								// If the required field is in the tree and does not have any children,
								// do nothing.
								continue;
							}
							// Add required field in the children to the tree if the field is message.
							if (field->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE) {
								AddRequiredFieldPath(child, field->message_type());
							}
						}
						else if (field->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE) {
							std::map<string, Node*>::const_iterator it =
								node->children.find(field->name());
							if (it != node->children.end()) {
								// Add required fields in the children to the
								// tree if the field is a message and present in the tree.
								Node* child = it->second;
								if (!child->children.empty()) {
									AddRequiredFieldPath(child, field->message_type());
								}
							}
						}
					}
				}

				void FieldMaskTree::TrimMessage(const Node* node, Message* message) {
					GOOGLE_DCHECK(!node->children.empty());
					const Reflection* reflection = message->GetReflection();
					const Descriptor* descriptor = message->GetDescriptor();
					const int32 field_count = descriptor->field_count();
					for (int index = 0; index < field_count; ++index) {
						const FieldDescriptor* field = descriptor->field(index);
						std::map<string, Node*>::const_iterator it =
							node->children.find(field->name());
						if (it == node->children.end()) {
							reflection->ClearField(message, field);
						}
						else {
							if (field->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE) {
								Node* child = it->second;
								if (!child->children.empty() && reflection->HasField(*message, field)) {
									TrimMessage(child, reflection->MutableMessage(message, field));
								}
							}
						}
					}
				}

			}  // namespace

			void FieldMaskUtil::ToCanonicalForm(const FieldMask& mask, FieldMask* out) {
				FieldMaskTree tree;
				tree.MergeFromFieldMask(mask);
				out->Clear();
				tree.MergeToFieldMask(out);
			}

			void FieldMaskUtil::Union(const FieldMask& mask1, const FieldMask& mask2,
				FieldMask* out) {
				FieldMaskTree tree;
				tree.MergeFromFieldMask(mask1);
				tree.MergeFromFieldMask(mask2);
				out->Clear();
				tree.MergeToFieldMask(out);
			}

			void FieldMaskUtil::Intersect(const FieldMask& mask1, const FieldMask& mask2,
				FieldMask* out) {
				FieldMaskTree tree, intersection;
				tree.MergeFromFieldMask(mask1);
				for (int i = 0; i < mask2.paths_size(); ++i) {
					tree.IntersectPath(mask2.paths(i), &intersection);
				}
				out->Clear();
				intersection.MergeToFieldMask(out);
			}

			void FieldMaskUtil::InternalSubtract(const Descriptor* descriptor,
				const FieldMask& mask1,
				const FieldMask& mask2, FieldMask* out) {
				if (mask1.paths().empty()) {
					out->Clear();
					return;
				}
				FieldMaskTree tree;
				tree.MergeFromFieldMask(mask1);
				for (int i = 0; i < mask2.paths_size(); ++i) {
					tree.RemovePath(mask2.paths(i), descriptor);
				}
				out->Clear();
				tree.MergeToFieldMask(out);
			}

			bool FieldMaskUtil::IsPathInFieldMask(StringPiece path, const FieldMask& mask) {
				for (int i = 0; i < mask.paths_size(); ++i) {
					const string& mask_path = mask.paths(i);
					if (path == mask_path) {
						return true;
					}
					else if (mask_path.length() < path.length()) {
						// Also check whether mask.paths(i) is a prefix of path.
						if (path.substr(0, mask_path.length() + 1).compare(mask_path + ".") ==
							0) {
							return true;
						}
					}
				}
				return false;
			}

			void FieldMaskUtil::MergeMessageTo(const Message& source, const FieldMask& mask,
				const MergeOptions& options,
				Message* destination) {
				GOOGLE_CHECK(source.GetDescriptor() == destination->GetDescriptor());
				// Build a FieldMaskTree and walk through the tree to merge all specified
				// fields.
				FieldMaskTree tree;
				tree.MergeFromFieldMask(mask);
				tree.MergeMessage(source, options, destination);
			}

			void FieldMaskUtil::TrimMessage(const FieldMask& mask, Message* destination) {
				// Build a FieldMaskTree and walk through the tree to merge all specified
				// fields.
				FieldMaskTree tree;
				tree.MergeFromFieldMask(mask);
				tree.TrimMessage(GOOGLE_CHECK_NOTNULL(destination));
			}

			void FieldMaskUtil::TrimMessage(const FieldMask& mask, Message* destination,
				const TrimOptions& options) {
				// Build a FieldMaskTree and walk through the tree to merge all specified
				// fields.
				FieldMaskTree tree;
				tree.MergeFromFieldMask(mask);
				// If keep_required_fields is true, implicitely add required fields of
				// a message present in the tree to prevent from trimming.
				if (options.keep_required_fields()) {
					tree.AddRequiredFieldPath(GOOGLE_CHECK_NOTNULL(destination->GetDescriptor()));
				}
				tree.TrimMessage(GOOGLE_CHECK_NOTNULL(destination));
			}

		}  // namespace util
	}  // namespace protobuf
}  // namespace google
